package nz.ac.massey.groupproject.ecs2;

import java.util.ArrayList;

/*
 * All collidable shapes in our game are polygons.
 *
 * Currently, all polygons are convex.  If we need concave polygons in the future, we can break
 * them down to convex polygons. This should be fine as long as all shapes have a non-zero area.
 * (Otherwise a point can sneak in between the crack.)
 *
 * Currently, all polygons are explicit.  In the future, We may need implicit polygons to
 * approximate circles.  We will not worry about that for now.
 *
 * Explicit polygons are represented by the Polygon class.
 */

/*
 * Convex polygon represented by a list of vertices.  Not degenerate polygon (area > 0).
 * No 2 points overlap. No 3 points are colinear.
 *
 * Vertices are sorted counter-clockwise.  The first point is farthest down (if two points are
 * equally low, the first point is the one to the left).
 *
 * The above is equivalent to sorting all edges by direction (0 ≤ angle < 360).
 *
 * XXX None of these constraints are checked by constructors. Caller must make sure they pass in valid data.
 * TODO check in DEBUG build
 *
 * In addition, we store the index of the point farthest up (break ties by picking the one to
 * the right) for quick 180 degree rotation.
 */
public final class Polygon {
	public final ArrayList<Vec2l>   vs;
	public final int                opposite_index;


	// ======================================== ctors ========================================
	public Polygon(long... coors)  { this(scalarpairsToVecs(coors)); }

	public Polygon(ArrayList<Vec2l> vertices) {
		vs = vertices;

		int topIndex = 0;
		for (int i = 1; i < vs.size(); i++) {
			var ydiff = vs.get(i).y - vs.get(topIndex).y;
			var xdiff = vs.get(i).x - vs.get(topIndex).x;
			if (ydiff > 0 || (ydiff == 0 && xdiff > 0))
				topIndex = i;
		}
		opposite_index = topIndex;
	}

	private static ArrayList<Vec2l> scalarpairsToVecs(long[] coors) {
		if (coors.length % 2 != 0) throw new RuntimeException("Internal Error: Polygon constructor called with odd number of arguments");

		var vertices = new ArrayList<Vec2l>(coors.length / 2);
		for (int i = 0; i < coors.length / 2; ++i) {
			vertices.add( new Vec2l(coors[i*2], coors[i*2+1]) );
		}
		return vertices;
	}




	// ======================================== heavy lifting ========================================
	/*
	 * Return 1 if point is outside.
	 * Return -1 if point is strictly inside.
	 * Return 0 if point is on the border.
	 *
	 * O(N)
	 */
	public int whereIs(Vec2l point) {
		final int n = vs.size();

		boolean strictlyInside = true;

		for (int i = 0; i < n; i++) {
			final Vec2l P = vs.get(  i  );
			final Vec2l Q = vs.get( (i+1)%n );
			final long cprod =  point.sub(P) .cprod( Q.sub(P) );
			if (cprod > 0) return 1;
			if (cprod == 0) strictlyInside = false;
		}

		return strictlyInside ? -1 : 0;
	}

	/*
	Compute Minkowski difference, which is used in collision detection.

	O(N) gift wrapping (sort of)
	TODO there's likely a way to compute partial hull in O(logN) time instead of doing the full hull in O(N).

	===== What is Minkowski difference =====
	Think of a solid shape as a mathematical set of points.
	The Minkowski difference between two shapes is defined as:

		minkowski_sum(shapeA, -shapeB)  =  { offset = a - b  |  ∀ a in shapeA,  b in shapeB }.

	===== How to use Minkowski difference =====
	Two shapes intersect iff Minkowski difference contains the origin.

	At time t, minkowski_sum(moved wall, -moved obj) contains O
	      <=>  minkowski_sum(init wall, -init obj) contains C = t * (velobj - velwall)

	Imagine inflating the wall and deflating the obj until the obj becomes a single dot.
	Also imagine moving the entire world to a new reference frame.  Now our little dot starts at the
	origin and travels at velocity vrel = vobj - vwall, and the wall is stationary.
	To avoid confusion, we will call the new object C, and the new wall "redzone".
	The original obj collides with the original wall iff C goes in redzone in this converted problem.

	Now we just wanna know whether C runs into redzone and if so, the earliest time of intersection.

	===== TODO explain the rest =====
	*/
	public static Polygon minkowskiDiff(Polygon sa, Polygon sb) {
		int lenA = sa.vs.size();
		int lenB = sb.vs.size();
		var newVertices = new ArrayList<Vec2l>( lenA + lenB );

		for ( int ia = 0, ib = sb.opposite_index
		    ; !(ia == lenA && ib == lenB + sb.opposite_index)
		    ; )
		{
			var P  = sa.vs.get(  ia    % lenA );
			var Q  = sb.vs.get(  ib    % lenB ).neg();
			var Pn = sa.vs.get( (ia+1) % lenA );
			var Qn = sb.vs.get( (ib+1) % lenB ).neg();

			newVertices.add( P.add(Q) );

			long dircmp = (Pn.sub(P))  .cprod  (Qn.sub(Q));
			if (dircmp >= 0) ia++;
			if (dircmp <= 0) ib++;
		}

		// We don't shrink ArrayList because it's not gonna live long.
		return new Polygon(newVertices);
	}
}
